/**
 *
 * Titre du TP : TP2
 *
 * Nom  : NGUYEN
 * Prenom : Quang Hoang
 *
 * Remarques :
 */
#include<stdio.h>
#include<stdlib.h>
#include <sys/sysinfo.h>
#include "fifo.h"
#include "graph.h"

static GRAPH *G;
static fifo * myfifo; // fifo using in bfs
struct sysinfo myinfo;

long getFreeRam(){
	  sysinfo(&myinfo);
//	  printf("freeram: %ld\n", myinfo.freeram/1024);
	  return myinfo.freeram;
}


int sort(const void *x, const void *y) {
  return (*(int*)y - *(int*)x);
}

long bfs(long v0, long * distance, long * pere){

	long subGraphSize = 1; //at least if self in the sub graph
	long i;
	long u;
	long v;

	fifo_clear(myfifo);

	fifo_add(myfifo, v0);

	pere[v0] = v0;

	while(fifo_empty(myfifo) != 0){
		u = fifo_extract(myfifo);
		for(i = 0; i < G->degrees[u] ; i++){
			v = G->links[u][i];
			if(pere[v] < 0){ //v non-visited
				fifo_add(myfifo, v);
				pere[v] = u;
				distance[v] = distance[u] + 1;
				subGraphSize++;
			}
		}
	}
	return subGraphSize;
}

int main(int argc, char** argv){

	long ramBefore = getFreeRam();

	// check for nbr of arguments passed
	FILE *f = fopen(argv[1], "r");

	long i = 0;

	G = graph_from_file(f, atol(argv[2]));
	fclose(f);

	printf("Nbr nodes : %ld\nNbr links : %ld\n",G->n, G->m);

	//----------------- Initiate value ---------------//

	long N = G->n; // number of nodes in the file

	long * distance = malloc(N * sizeof(long));
	long * pere = malloc(N * sizeof(long));
	long * compSize = malloc(N * sizeof(long)); //subgraphs' size, maximum n components
	fifo mainfifo = fifo_create(N);
	myfifo = &mainfifo;

	long numComp = 0; // nbr of components of the graph

	for(i = 0; i < G->n; i++){
		pere[i] = -1; // node i non-visited
		compSize[i] = -1;
		distance[i] = 0;
	}

	//----------------- Number of components ---------------//
	for(i = 0; i < G->n; i++){
		if(pere[i] < 0){ // node i is not visited
			compSize[numComp] = bfs(i, distance, pere); //new subGraph non-visited, root=i
			numComp++; // increase the nbr of components
		}
	}

	long ramAfter = getFreeRam();

	printf("\n1.\n");

	if(numComp == 1){
		printf("The graph is connected\n");
	}
	printf("Nbr of components: %ld\nAverage size: %4.2f\n", numComp, (float)N/(float)numComp);
	printf("RAM consommation: %ld MB\n", (ramBefore - ramAfter)/1024/1024);

	//----------------- 3 max components -----------------//
	qsort(compSize, numComp, sizeof(long), sort);
	printf("Size of 3 max components: ");
	for(i = 0; i < 3; i++){
		printf("%ld ",compSize[i]);
	}
	printf("\n");

	free(compSize);

	//-------- Distances in BFS tree of one node -----------//
	//re-init
	for(i = 0; i < G->n; i++){
		pere[i] = -1; // node i non-visited
		distance[i] = 0;
	}
	printf("\n2. Distances on the BFS tree of node 0\n");
	long subGraphSize = bfs(0,distance,pere);
	printf("Component's size: %ld\n",subGraphSize);
	long sumDistance = 0;
	long maxDistance = 0;
	for(i=0 ; i<N; i++){
		if(pere[i] > -1){ //i visited
			sumDistance += distance[i];
			if(maxDistance < distance[i]){
				maxDistance = distance[i];
			}
		}
	}
	printf("Max Distance:  %ld\n", maxDistance);
	printf("Mean Distance: %4.2f\n", (float)sumDistance / (float)subGraphSize);

	free(pere);
	free(distance);

  return 0;
}

